A. Field of the Invention
This invention is related to the field of telecommunications and the process by which digital data is transmitted between computer systems over a telephone network or other communications link and a high speed computer network. The invention is particularly suitable for use in devices that support the forwarding of packetized data between two communications media where there is a significant speed differential between the two media. An example of such a device is a network access server (sometimes referred to in the art as a remote access server), where Internet Protocol (IP) or Internet Exchange Protocol (IPX) packets are exchanged between a high-speed local or wide area packet-switched data network and a low-speed dial-up Point-to-Point Protocol link, such as the public switched telephone network. The remote access server connects a remotely located personal computer or other terminal dialing in over a slow PSTN link to a computer or other source of data resident on the high-speed data network.
The present invention achieves an increase in throughput across the interface by dropping redundant packets, that is, dropping the packets entirely or, alternatively, dropping the (redundant) data present in packets going across the interface and transmitting the header for the redundant packet. By dropping redundant packets in the network access server that are en route to the remote terminal, in accordance with a principal aspect of the present invention, the speed and efficiency by which the remote terminal can download files or data from the high-speed network is improved since precious bandwidth on the low-speed link is not being wasted by transmission of packets that have already been received by the remote terminal. The invention can be used in many different application, such as Internet or corporate network access for users dialing in to a network computer over low speed links, e.g., voice grade telephone circuits.
B. Description of Related Art
In order for communication between two computers over a communications medium to be possible, the computers and the equipment in the medium connecting the computers together must follow certain rules or procedures, known in the art as protocols. The communications industry has standards bodies that adopt protocols to govern many different aspects of data communication. These protocols can be modeled as a hierarchy of levels, sometimes referred to as the Open Systems Interface (OSI) model. The lowest level concerns the physical medium connecting the computers together. Above this layer in the model are protocols related to media access control, data link, network, transport, session, presentation, and application features, in ascending order.
Transport layer networking protocols use a variety of techniques to achieve reliable delivery of data. All rely on some form of acknowledgement and retransmission paradigm of some sort. The most common method is to utilize a sliding window protocol with some form of end-to-end acknowledgement required to advance the transmitter""s window. Intermediate nodes between the two computers (such as routers) do not participate in the algorithm as they typically provide only network layer services (packet forwarding).
For example, a transport protocol known as Transmission Control Protocol uses a scheme where the receiving endpoint transmits a cumulative acknowledgment of all contiguous data properly received, as well as the currently allowed receive window size (which varies over time), to the transmitting endpoint. The transmitting endpoint uses this feedback information to select what data to (re)transmit. This scheme provides flow control as well as reliable transfer. TCP uses an adaptive retransmission algorithm that is driven based on estimated round-trip times for acknowledgments.
For unicast transport-level flows, packets are generated on the source node, passed through various intermediate nodes, e.g., routers, and finally arrive at the destination. In packet switched networks (such as the Internet), packets can arrive at the destination in order, out of order, more than once, or not at all. The same is true for intermediate nodes. There are two major differences between the intermediate and the destination nodes of a flow. Intermediate nodes are not typically notified of flow establishment/termination, and intermediate nodes do not generally generate feedback information to the source node of the flow. The function provided by most intermediate nodes is to simply forward packets.
In the present state of the art, advanced intermediate nodes are capable of grooming/shaping traffic based on dynamic network load and quality of service (QOS) criteria. This grooming/shaping function consists of reordering packets and selecting packets to drop. Basically, the grooming/shaping function is a scheme to arbitrate the use of congestion points in the network and to provide certain users increased throughput, lower latency, or higher reliability. These types of functions are usually deployed in networks that are over-provisioned. Networks maintained by Internet Service Providers (ISPs) are a common example of an over-provisioned network. They sell more network capacity than they have based on statistical usage patterns to generate revenues.
To perform this grooming/shaping function, intermediate nodes must perform some packet queuing. This queuing allows the nodes to deal with xe2x80x9cburstyxe2x80x9d traffic without loss of packets. The amount of queuing introduced in a router directly effects maximum forwarding latency (transit delay) and its ability to deal with periods of time where use of an interface on the router is oversubscribed. In general, routers attempt to minimize queuing, as reducing the amount of forwarding latency to a minimum is an overriding concern.
Most users connect to the Internet at the network layer via low-speed modems ( less than 128 Kbps) using the Internet Protocol version 4 (iPv4), encapsulated by the Point To Point Protocol (PPP). The user""s phone calls are routed from the public switched telephone network onto the ISP networks via a device known as a Network Access Server (NAS). A representative network access server is described in the patent to Dale M. Walsh, et al., U.S. Pat. No. 5,528,595, which is incorporated by reference herein. The NAS is connected via a high-speed LAN or WAN interface to the Internet and to the user via a relatively low speed PPP modem connection over the public switched telephone network, cellular telephone network or other communications medium. Network access servers similar in architecture and functionality of the above-referenced Walsh et al. patent are currently commercially available from. 3Com Corporation, the assignee of the present invention, and from other vendors in the industry.
It is a widely recognized truism that a user""s desired bandwidth for network access (e.g., Internet or corporate network access) is almost always greater than the available bandwidth provided by the modem link. It is also a truism that for most remote access applications, including Internet access, the flow of information and data from the computer on the network to the remote terminal or user is typically much-greater than the flow of data going in the opposite direction. While asymmetrical communications techniques, such as the V.90 56 K technology, help somewhat, this phenomenon usually results in a significant queuing of data directed from the high-speed LAN/WAN interface towards the low-speed modem interface. Moreover, the PPP/modem connection linking the remote user or terminal to the network access server is the bottleneck limiting bandwidth in most remote access scenarios, since the maximum speed of dial-up network access servers is 56 Kbps over a conventional phone line (asymmetrical digital subscriber line (ADSL) and other less common techniques excluded), whereas the transmission rates on the data network is order of magnitudes faster.
Numerous approaches have been proposed in the art to address this bandwidth bottleneck issue. These approaches included faster modem modulation schemes, such as the 56 Kbps technique adopted in the ITU-T V.90 standard, modem data compression in accordance with the V.42 bis Standard, PPP header compression, ADSL and other asymmetric techniques, Van Jacobson""s TCP/IP header compression for PPP, and PPP data compression schemes promoted by Microsoft Corporation and STAC Electronics. Obviously, this is a critical problem.
Much of the network traffic directed towards the remote user is Transmission Control Protocol (TCP) traffic. Fortunately, TCP contains congestion avoidance algorithms to prevent large numbers of dropped packets (due to finite data queuing in the NAS) and retransmissions, thus preventing xe2x80x9ccongestion collapsexe2x80x9d of the user""s PPP modem link. TCP also maintains a transmit congestion avoidance window and round-trip acknowledgement (ACK) timers for each connection. When TCP determines congestion is likely, TCP reduces both traffic, as well as retransmissions, exponentially. When a connection starts, or after a period of congestion, TCP uses the slow-start algorithm in conjunction with other congestion avoidance algorithms to limit increasing transmit limits too quickly, which Would result in more congestion. These algorithms work quite well after a TCP connection has been established and operational for a while. However, typical user traffic (like the HTTP traffic generated when surfing the Internet) starts numerous short-lived TCP connections. The server""s TCP implementations have to re-adapt on each successive connection. This can cause periods of brief congestion due to retransmits.
As a result of all of the above considerations, a remote user connected over a low speed link to a high speed network such as the Internet experiences markedly slower transfer of data then that theoretically achievable, resulting in inconvenience, annoyance and frustration. Furthermnore, if the user continues to initiate short-lived TCP connections, the problem is only exacerbated by causing additional congestion and transmission of relatively large numbers of redundant packets. Consequently, the bandwidth of the low-speed link between the remote terminal and the network access server is very inefficiently utilized, exacerbating the problem of the user experiencing poor quality of remote access service. These problems are particularly acute for persons using conventional analog lines to access the network. Heretofore, persons working in the art have not succeeded in satisfactorily addressing all of these issues.
It is an object of the invention to address, at least in part, these problems and improve the efficiency and throughput of data through a device such as a network access server providing an interface between two networks (such as the PSTN and a high speed packet switched network) which are subject to differences in their respective nominal nominal transmission rates. The present invention is particularly suitable for use in network access servers or other nodes that provide an interface between a relatively slow transmission medium and a relatively fast transmission medium, such as a server providing network access for users dialing into a high speed IP network such as an Ethernet network or Internet over a voice grade analog telephone circuit.
A method is provided for increasing the throughput of data through a device providing an interface between a telephone line and a data network. For example, the method may increase the throughput through a network access server maintained by an Internet Service Provider, with the network access server providing Internet access for remote terminals over the public switched telephone network.
The method comprises the step of first receiving a packet of data from the high speed network at the interface. The packet will typically be placed in a queue for processing, the queue referred to herein alternatively a xe2x80x9cfirst queuexe2x80x9d or xe2x80x9cqueue Axe2x80x9d. The packet of data may be for example a packet of data from a host computer on the Internet en route to the remote terminal. The network access server then determines if the packet of data is a duplicate of a packet previously forwarded across the interface to the recipient of the packet, such as a retransmission of the packet. The network access server drops the packet if the packet is a duplicate of a packet previously forwarded across the interface or already present in the queue, rather than queuing it for transmission. Several techniques for determining whether the packet is a redundant/retransmitted packet are described. Almost certainly, had this packet been transmitted the packet would have been dropped upon receipt by the remote terminal as a duplicate. This is an expensive waste of bandwidth at the portion of the packet path that can least afford it. The method will typically require that the link layer protocol (e.g. PPP) track which TCP packets have yet to be transmitted via the modem in the network access server to the remote terminal, so as to ensure that non-redundant packets are not dropped and provide a mechanism for determining whether the packet is a redundant or retransmitted packet or not.
As an alternative or second embodiment (which may be practiced alone or in conjunction with the above first method), the network access server maintains a second queue, referred to herein alternatively as xe2x80x9cqueue Bxe2x80x9d for packets en route through the interface from the remote terminal to the host system on the network. Every packet going from the remote terminal (i.e, the PPP link) to the host computer system (i.e., the high speed WAN/LAN, e.g. Ethernet) link is placed in the second queue. The method involves examining the TCP acknowledge sequence number of the packets in the xe2x80x9cqueue Bxe2x80x9d being sent to the host system on the network. The method further involves looking at the packet sequence numbers for packets in the first-queue (xe2x80x9cqueue Axe2x80x9d). The method takes advantage of the fact that the packets in the second queue will contain an acknowledgement sequence number (referred to as ACK herein) indicating which packets have been received by the remote terminal. If a packet is present in queue A for which an acknowledgment that such packet has already been received exists (determined from inspection of the acknowledge sequence numbers of the packets in the second queue), then the packet in queue A can be safely dropped.
Alternatively, and more preferably, the data portion of the packet in queue A is dropped and only the packet header, including the acknowledge sequence number, is sent. This is because the header may contain new, i.e., not previously received, information, e.g., acknowledgement information, that the other end may need to operate in accordance with a communications protocol such as TCP. Furthermore, the number of bytes needed for the header it typically minimal compared to the amount of bytes devoted to the data or payload portion of the packet. Therefore substantial savings of bandwidth will still be obtained in the situation in which the redundant data is dropped by the header with a payload of zero bytes (a valid packet) is sent.
The method may also be done in a manner in which information is stored as to which packets have already been transmitted across the interface. Instead of merely dropping duplicates of packets that happen to be present in the first queue at the same time, any packet in the first queue for which an acknowledgement has already been received is automatically dropped. This would typically require a storing of the packet sequence numbers for the acknowledged packets in a memory, continually updating the memory as new acknowledgements are received, and then checking the packets in the first queue to determine whether an acknowledgement for the packets in the queue has been received. If so, the packet is dropped. Again, in this method the entire packet may be dropped, or, more preferably, the data portion of the packet is dropped and only the header for the packet is transmitted as an acknowledgement packet.
Any or all of the above methods prevent re-transmitting data, or entire packets, over the slow PPP link connecting the network access server to the remote terminal. Moreover, the method, in particular the second embodiment, prevents the remote terminal""s TCP state machine from thinking that it""s ACKs are not-getting through the telephone or data networks to the host system, and therefore prevents it from going into a congestion control mode. The congestion control mode is a back-off algorithm that will slow down the packet stream over the PPP link to the network access server and host system by causing the remote terminal to reduce its packet flow. By preventing the remote terminal from going into congestion control mode, the throughput is further improved.
Further details on these and many other aspects of the present invention will become apparent from the following detailed description of a presently preferred embodiment of the invention.